1. Field of the Invention
This invention relates to split private key cryptosystem and more particularly to an improved system and method for session key distribution, privacy enhanced messaging and information distribution using a split private key cryptosystem.
2. Description of the Related Art
Cryptosystems have been developed for maintaining the privacy of information transmitted across a communications channel. Typically, a symmetric cryptosystem is used for this purpose. Symmetric cryptosystems, which utilize electronic keys, can be likened to a physical security system where a box has a single locking mechanism with a single key hole. One key holder uses his/her key to open the box, place a message in the box and relock the box. Only a second holder of the identical copy of the key can unlock the box and retrieve the message. The term symmetric reflects the fact that both users must have identical keys.
In more technical terms, a symmetric cryptosystem consist of an encryption function E, a decryption function D, and a shared secret-key, K. The key is a unique string of data bits to which the functions are applied. Two examples of encipherment/deencipherment functions are the National Bureau of Standards Data Encryption Standard (DES) and the more recent Fast Encipherment Algorithm (FEAL). To transmit a message, M, in privacy, the sender computes M=E (C,K), where C is referred to as the ciphertext. Upon receipt of C, the recipient computes M=D (C,K), to recover the message M. An eavesdropper who copies C, but does not know K, will find it practically impossible to recover M. Typically, all details of the enciphering and deciphering functions, E and D, are well known, and the security of the system depends solely on maintaining the secrecy of key, K. Conventional symmetric cryptosystems are fairly efficient and can be used for encryption at fairly high data rates, especially if appropriate hardware implementations are used.
Asymmetric cryptosystems, often referred to as public key cryptosystems, provide another means of encrypting information. Such systems differ from symmetric systems in that, in terms of physical analogue, the box has one lock with two non-identical keys associated with it. Either key can be used to unlock the box to retrieve a message which has been locked in the box by the other key.
In public key electronic cryptosystems, each entity, has a private key, d, which is known only to the entity, and a public key, e, which is publicly known. Once a message is encrypted with a user's public-key, it can only be decrypted using that user's private-key, and conversely, if a message is encrypted with a user's private-key, it can only be decrypted using that user's public-key. It will be understood by those familiar with the art that although the terms "encrypt" and "decrypt" and derivations thereof are used herein in describing the use of public and private keys in an asymmetric public key cryptosystem, the term "transform" is commonly used in the art interchangeably with the term "encrypt" and the term "invert" is commonly used in the art interchangeably with the term "decrypt". Accordingly, as used herein in describing the use of public and private keys, the term "transform" could be substituted for the term "encrypt" and the term "invert" could be substituted for the term "decrypt".
If sender x wishes to send a message to receiver y, then x, "looks-up" y's public key e, and computes M=E(C,e.sub.y) and sends it to y. User y can recover M using its private-key d.sub.y, by computing M=D(C,d.sub.y). An adversary who makes a copy of C, but does not have d.sub.y, cannot recover M. However, public-key cryptosystems are inefficient for large messages.
Public-key cryptosystems are quite useful for digital signatures. The signer, x, computes S=E(M, d.sub.x) and sends [M,S] to y. User y "looks-up" x's public-key e.sub.x, and then checks to see if M=D(S,e.sub.x). If it does, then y can be confident that x signed the message, since computing S, such that M=D(S, e.sub.x), requires knowledge of d.sub.x, x's private key, which only x knows.
Public-key cryptography also provides a convenient way of performing session key exchange, after which the key that was exchanged can be used for encrypting messages during the course of a particular communications session and then destroyed, though this can vary depending on the application.
One public key cryptographic system is the Rivest, Shamir, Adleman (RSA) system, as described in Rivest, Shamir and Adleman, "A Method of Obtaining Digital Signatures and Public Key Cryptosystems", CACM, Vol 21, pp 120-126, February 1978. RSA is a public-key based cryptosystem that is believed to be very difficult to break. In the RSA system the pair (e.sub.i N.sub.i), is user i's public-key and d.sub.i is the user's private key. Here N.sub.i =pq, where p and q are large primes. Here also e.sub.i d.sub.i =1mod.phi.(N.sub.i), where .phi.(N.sub.i)=(p-1)(q-1) which is the Euler Toitient function which returns the number of positive numbers less than N.sub.i, that are relatively prime to N.sub.i. A Carmichael function is sometimes used in lieu of a Euler Toitient function.
To encrypt a message being sent to user j, user i will compute C=M.sup.(e.sbsp.j.sup.) modN.sub.j and send C to user j. User j can then perform M=C.sup.(d.sbsp.j.sup.) modN.sub.j to recover M. User i could also send the message using his signature. The RSA based signature of user i on the message, M, is M.sup.d.sbsp.i modN.sub.i. The recipient of the message, user j, can perform M.sup.(d.sbsp.i.sup.) modN.sub.i .sup.(e.sbsp.i.sup.) modN.sub.i, to verify the signature of i on M.
In a typical mode of operation, i sends j, M.sup.(d.sbsp.i.sup.) modN.sub.i along with M and a certificate C=(i,e.sub.i N.sub.i) (d.sub.CA)modN.sub.CA, where C is generated by a Certificate Authority (CA) which serves as a trusted off-line intermediary. User j can recover i's public key from C, by performing C.sup.(e.sbsp.CA.sup.))modN.sub.CA, as e.sub.CA and N.sub.CA are universally known. It should also be noted that in an RSA system the encryption and signatures can be combined.
Modifications to RSA systems have been proposed to enable multi-signatures to be implemented. Such an approach is described in Digital Multisignature, C. Boyd, Proceedings of the Inst. of Math, and its Appl. on Cryptography and Coding, Dec. 15-17, 1986. The proposed approach extends the RSA system by dividing or splitting the user private key d into two portions, say d.sub.i and d.sub.j, where d.sub.i *d.sub.j =d.
Recently an improved system and method for split key public encryption has been disclosed using a split private key, see U.S. patent application Ser. No. 08/277,808 filed on Jul. 20, 1994 for Y. Yacobi and R. Ganesan entitled "A System and Method for Identity Verificiation, Forming Joint Signatures and Session Key Agreement in an RSA Public Cryptosystem". The described system and method, allow two system users to verify each other's identity, form a joint signature and establish and distribute a session key in an RSA environment.
The system and method developed by Yacobi and Ganesan provides significant benefits where no intermediary between the users needs to be empowered with the ability to ease drop on encrypted communications. However, in practical systems, it is often desirable or required, for reasons other than security, that an intermediary with such power be placed between the users. Such an intermediary can provide a central point of audit and service cancellation, as well as other benefits. For example, public subscription systems, such as public electronic mail systems, will normally have a central intermediary empowered to monitor the access of a subscriber and terminate access should a subscriber fail to pay his monthly access fee. However, those conventional systems lack the capability to easily and promptly authorize a user's access to the system and distribute a session key or implement lawful wiretaps, privacy enhanced messaging and secure message distribution.
Therefore, it is an object of the invention to provide a system and method using split private key public encryption which facilitates confirmation of a user's authorized access to another user of the system by a central intermediary each time a communication is initiated.
It is a still further object of the present invention to provide a method and system using split private key public encryption to facilitate distribution of session keys through a central intermediary.
It is also an object of the invention to provide a method and system for session key distribution by a central intermediary using split private key encryption which facilitates the authorization and implementation of lawful wiretaps, privacy enhanced messaging and secure message distribution.
Additional objects, advantages and novel features of the present invention will become apparent to those skilled in the art from the following detailed description, as well as by practice of the invention. While the invention is described below with reference to preferred embodiments, it should be understood that the invention is not limited thereto. Those of ordinary skill in the art having access to the teachings herein will recognize additional applications, modifications and embodiments in other fields which are within the scope of the invention as disclosed and claimed herein and with respect to which the invention could be of significant utility.